package tree;

import commons.TreeNode;

/**
 * leet-code(617) 合并二叉树
 *
 * @author Ringo
 * @date 2021/9/12 20:50
 */
public class MergeTrees {

    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        return merge(root1, root2);
    }

    public static TreeNode merge(TreeNode x1, TreeNode x2) {
        if (x1 == null) return x2;
        if (x2 == null) return x1;

        x1.val += x2.val;

        x1.left = merge(x1.left, x2.left);
        x1.right = merge(x1.right, x2.right);
        return x1;
    }


    // 合并后不修改原来的树结构
    public static TreeNode merge1(TreeNode x1, TreeNode x2) {
        if (x1 == null && x2 == null)
            return null;
        TreeNode root = new TreeNode((x1 == null ? 0 : x1.val) + (x2 == null ? 0 : x2.val));
        root.left = merge1(x1 == null ? null : x1.left, x2 == null ? null : x2.left);
        root.right = merge1(x1 == null ? null : x1.right, x2 == null ? null : x2.right);
        return root;
    }

}
